#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <dirent.h>
#include <inttypes.h>
#include <sys/types.h>
#include <sys/stat.h>

#define	SHA1SIZE	20

/* return the routing key for a SHA1 digest */
uint32_t keyroute(uint8_t sha1[SHA1SIZE])
{
	uint32_t sum;
	size_t i;
	for (i = 0, sum = 0; i < SHA1SIZE; i++)
		sum += sha1[i];
	sum = sum + (sum >> 8);
	return (sum + (sum >> 4)) & 0x0f;
}

int hex2sha1(uint8_t sha1[SHA1SIZE], const char *src)
{
	int i;

	for (i = 0; i < 2*SHA1SIZE; i++) {
		sha1[i/2] *= 16;
		if (src[i] >= '0' && src[i] <= '9') {
			sha1[i/2] |= src[i] - '0';
		} else if (src[i] >= 'a' && src[i] <= 'f') {
			sha1[i/2] |= src[i] - 'a' + 10;
		} else if (src[i] >= 'A' && src[i] <= 'F') {
			sha1[i/2] |= src[i] - 'A' + 10;
		} else {
			return -1;
		}
	}

	return 0;
}

int walk_tree(char *path)
{
	char *filename;
	char **paths;
	int i, pathcnt = 0, pathmax = 2;
	DIR *dir;
	struct dirent *de;
	struct stat st;
	uint8_t sha1[SHA1SIZE];

	filename = calloc(256, sizeof(char));

	paths = calloc(pathmax, sizeof(char *));
	paths[pathcnt++] = strdup(path);
	for (i = 0; i < pathcnt; i++) {
		dir = opendir(paths[i]);
		if (NULL == dir) {
			fprintf(stderr, "opendir(%s) failed (%s)\n",
				paths[i], strerror(errno));
			return -1;
		}
		while (NULL != (de = readdir(dir))) {
			if (0 == strcmp(de->d_name, "."))
				continue;
			if (0 == strcmp(de->d_name, ".."))
				continue;
			sprintf(filename, "%s/%s", paths[i], de->d_name);
			if (0 != stat(filename, &st)) {
				fprintf(stderr, "stat(%s) failed (%s)\n",
					filename, strerror(errno));
				continue;
			}
			if (S_ISDIR(st.st_mode)) {
				if (pathcnt >= pathmax) {
					pathmax *= 2;
					paths = realloc(paths, pathmax * sizeof(char *));
					memset(&paths[pathcnt], 0,
						(pathmax - pathcnt) * sizeof(char *));
				}
				/* add another directory */
				paths[pathcnt++] = strdup(filename);
				continue;
			}
			if (0 != hex2sha1(sha1, de->d_name)) {
				fprintf(stderr, "error converting '%s'\n", de->d_name);
				continue;
			}
			printf("%x %s\n", keyroute(sha1), filename);
		}
		closedir(dir);
	}
	return 0;
}

int main(int ac, char **av)
{
	uint8_t sha1[SHA1SIZE];
	char *name;
	struct stat st;

	if (ac < 2) {
		fprintf(stderr, "usage: %s filename\n", av[0]);
		exit(1);
	}

	if (0 == stat(av[1], &st) && S_ISDIR(st.st_mode)) {
		return walk_tree(av[1]);
	}

	name = strrchr(av[1], '/');
	name = (NULL == name) ? av[1] : name + 1;

	if (0 != hex2sha1(sha1, name)) {
		fprintf(stderr, "error converting '%s'\n", av[1]);
		exit(1);
	}

	printf("%x %s\n", keyroute(sha1), av[1]);
	return 0;
}
